Type-safe languages such as Java® ensure characteristics that cause neither invalid memory access nor an unusual termination of a program that is not intended by the programmer. Accordingly, a type-safe language does not allow any invalid memory access and as a result does not cause execution that may cause a program crash. These characteristics of type-safe languages have sharply increased in importance in recent years for security reasons as well. To ensure these characteristics, a software-initiated potentially excepting instructions (S-PEI) that ensures that a program would not terminate must precedes a hardware-initiated potentially excepting instructions (H-PEI), such as a memory access instruction with an invalid address or a Translation Lookaside Buffer (TLB) error. That is, dependency occurs between the instructions in that that an exception check instruction must be executed before a memory access can be executed.
Such dependencies as well as data dependencies and control dependencies in general contained in programs may hinder optimization that changes instruction execution sequence. Speculative execution is known that allows instructions to be reordered. Speculative execution is execution of an instruction before it is determined that the program should be executed. In such a case, a memory access instruction with an invalid value can be executed, therefore a system must support execution that inhibits exception occurrences.
Because a large number of exception instructions are contained in a program written in a type-safe program, speculative instructions are applied more often than a program written in a non-type-safe program such as C or Fortran. However, no methods are known for efficiently applying speculative execution relating to exception check instructions in non-type-safe languages while ensuring reduction in program execution time.
In a program in languages that require precise exception semantics, it must be ensured that the order of S-PEI occurrences is not changed after optimization of the program, therefore in general the optimization that changes the execution sequence of S-PEIs is not simple.
Speculative execution (prior-art reference 1: M. D. Smith, M. S. Lam, and M. A. Horowitz, “Boosting Beyond Static Scheduling in a Superscalar Processor” in Proceedings of the 17th Annual International Symposium on Computer Architecture, pp. 344–354, 1990) is known, which is a method for speeding up the execution of a program by executing an instruction before it is determined that actual execution of that program will be successfully accomplished. Two main speculative execution methods are known. One is a control speculation (prior-art reference 2: S. A. Mahlke, W. Y. Chen, R. A. Bringmann, R. E. Hank, W. W. Hwu, B. R. Rau, and M. S. Schlansker, “Sentinel scheduling: A model for compiler-controlled speculative execution,” ACM Transactions on Computer Systems, 11 (4), pp. 376–408, 1993). This method relaxes the control dependency between a branch instruction and the subsequent instruction. It allows a compiler to move an instruction that is frequently executed across a branch instruction. The other is data speculation (prior-art reference 3: D. M. Gallagher and W. Y. Chen and S. A. Mahlke and J. C. Gyllenhaal and W. W. Hwu, “Dynamic memory disambiguation using the memory conflict buffer,” in Proceedings of International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 183–193, 1994). This method relaxes the data dependency between a memory store instruction and a memory load instruction. A compiler assumes that a memory store instruction and a memory load instruction access different addresses and moves the load instruction and the subsequent instruction across the memory store instruction.
These studies on speculative execution address C and Fortran, which are not a type-safe language. The only study on speculative execution that addresses a type-safe language is “Exploring the interaction between Java®'s implicitly thrown exceptions and instruct” by M. Arnold, M. S. Hsiao, U. Kremer, and B. Ryder (prior-art reference 4). According to this sturdy, speculative execution across an S-PEI is performed by performing the following steps.                1. An S-PEI contained in a program is decomposed into a compare instruction and a branch instruction.        2. Create a super block having one control entry and more than one control exit.        3. A dependency graph is generated of which the nodes correspond to instructions, each of the nodes having two arcs, a data dependency and control dependency.        4. Instructions are moved within the super block across branch instructions by using general percolation. If an H-PEI is moved across a branch instruction, the H-PEI instruction is transformed into an instruction that can be speculatively executed. If an instruction is moved across a branch instruction, control dependencies are removed from the dependency graph.        5. List scheduling is performed in the dependency graph with consideration given to factors such as instruction latency.        
According to the method described in prior-art reference 4, an S-PEI is transformed into a compare instruction and a branch instruction which are used for ordinary conditional branching at step 1. Thus, it has the advantage that a conventional framework for super block scheduling can be used for branch instructions at step 2 and the subsequent steps. FIG. 1 shows an example of actual application. In FIG. 1, an exemplary program in a box at the top is written in Java® and programs in the second to fourth boxes are written in an assembly language. A compiler generates an intermediate representation from a source program provided to it. It then follows the above-described steps to generate a code that can be speculatively executed. First, it decomposes the S-PEI into a compare instruction and a branch instruction. In this example, a null check instruction is decomposed into a compare instruction (cmp) and a branch instruction (jmp). Then, it creates a super block and a dependency graph. It moves instructions across the branch instructions within the super block. Here, instructions, N5, N6, and N7 can be moved across the branch instruction N4. Because instruction N6 is an H-PEI, it is transformed into a speculative load instruction that inhibits an exception occurrence. (“Inhibiting an exception occurrence” means that exception occurrences are not communicated to a predetermined piece of hardware. Instead of communicating the occurrence of an exception, it is recorded in software.) In addition, the control dependencies of N4 on N5, N6, and N7 are removed. Because N8 is used as a sentinel instruction for checking an exception state of speculative execution, N8 cannot be moved across the branch instruction. In this example, if N8 is executed with the occurrence of an exception being inhibited in N6′, the instruction sequence is re-executed from N6′. Finally, list scheduling is performed with consideration given to factors such as instruction latency. In the following description with respect to the accompanying drawings, the assumption is that the instruction latency of a load instruction (ld) and a speculative load instruction (ld.s) is 3 and that of the other instructions is 1. The dependency graph shown in the right-hand part of the FIG. 2 corresponds to the intermediate representation of the compiler shown in FIG. 1 before the check instruction is decomposed and the dependency graph shown in the right-hand part of FIG. 2 corresponds to the intermediate representation of the compiler shown in FIG. 1 to which the list scheduling has been applied.
Guarded Program dependency graph (GPDG) (prior-art reference 5: Koseki, Komatsu, and Fukazawa, “Global code scheduling technique and its evaluation,” Joint Symposium on Parallel Processing, 1994, pp. 1–8, 1994) is known, which is another method that uses speculative execution by removing arcs. The GPDG is a graph that consists of nodes corresponding to instructions and arcs representing dependencies, data dependencies, and resource dependencies. The graph can represent the execution time of a program and can address control speculation by removing control dependent arcs. However, it does express constraints imposed by exceptions. There is a study for relaxing the order in which exceptions occur (prior-art reference 6: Manish Gupta, Jong-Deok Choi, and Michael Hind, “Optimizing Java® programs in the presence of exceptions,” in Proceedings of the 14th European Conference on Object-Oriented Programming (ECOOP'00), pp. 422–446, 2000). Described in this study is optimization by analyzing the liveness of an enclosing exception handler to reorder instruction having a side effect and S-PEI and optimization that decomposes an S-PEI into an instruction checking an exception an instruction for causing an exception and keeps the order of occurrence of the S-PEIs proper to allow for reordering of instructions checking an exception.
In another known technology for relaxing the order in which exceptions occur (prior-art reference 7: U.S. patent application Ser. No. 10/020,656, now U.S. Pat. No. 6,931,635 of Inagaki and Komatsu, entitled “Method for providing mechanism for speculatively executing potentiality excepting institution and speculative exception handling mechanism,” an instruction that can generate exceptions due to S-PEIs is separated from an instruction for checking them to shorten a critical path. The dependency between the instruction for checking exception due to S-PEI and an H-PEI still remains. The prior art described in prior-art reference 4 has the following problems.                (a) Separation of an S-PEI into a general-purpose compare instruction and branch instruction can result in increases in the number of branches in a block, the complexity of expressive form of a program, and compiling time. In the example shown in FIG. 1, a branch instruction is generated in the intermediate representation, which is not contained in the original program. This can increase compiling time because it requires the consideration of moving an instruction across a branch instruction during, general percolation.        (b) An H-PEI essentially depends only on an S-PEI. However, because the S-PEI is decomposed into general-purpose branch instructions, the H-PEI comes to depend on all the subsequent instructions when generating a graph having data dependencies and control dependencies. Thus, unnecessary dependencies are produced. In the example shown in FIG. 1, the original null-check instruction guards the subsequent instruction ld r5=[r4] alone. However, because it is transformed into a general branch instruction, control dependencies on all the subsequent instructions are generated, thus producing unnecessary dependencies (see the dependency graph shown in the left-hand part of FIG. 2).        (c) Because precise execution time is not estimated, speculative code motion that does not reducing execution time can result. In the example shown in FIG. 1, because the instruction reordering using general percolation is performed before list scheduling which is performed with consideration given to instruction latency, all the instructions that can be moved are moved. Therefore, it is not ensured that this moving would reduce the execution time.        (d) When S-PEIs are decomposed into general purpose compare instructions and branch instructions, reordering of the S-PEI instructions means reordering of branch instructions, therefore it becomes difficult to optimize the reordering of the S-PEI instruction themselves.        